{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def fib(self, n: int) -> int:\n",
    "        if n <= 0:\n",
    "            return 0\n",
    "        pre1 = 0\n",
    "        pre2 = 1\n",
    "        i = 1\n",
    "        while i < n:\n",
    "            pre0 = pre1 % 1000000007\n",
    "            pre1 = pre2 % 1000000007\n",
    "            pre2 = (pre0 + pre1) % 1000000007\n",
    "            i += 1\n",
    "        \n",
    "        return pre2\n",
    "\n",
    "solution = Solution()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(0, 1, 1, 2, 3, 5, 8)"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "solution.fib(0), solution.fib(1), solution.fib(2), solution.fib(3), solution.fib(4), solution.fib(5), solution.fib(6)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2 1 0 1 True\n",
      "3 2 1 1 True\n",
      "4 3 1 2 True\n",
      "5 5 2 3 True\n",
      "6 8 3 5 True\n",
      "7 13 5 8 True\n",
      "8 21 8 13 True\n",
      "9 34 13 21 True\n",
      "10 55 21 34 True\n",
      "11 89 34 55 True\n",
      "12 144 55 89 True\n",
      "13 233 89 144 True\n",
      "14 377 144 233 True\n",
      "15 610 233 377 True\n",
      "16 987 377 610 True\n",
      "17 1597 610 987 True\n",
      "18 2584 987 1597 True\n",
      "19 4181 1597 2584 True\n",
      "20 6765 2584 4181 True\n",
      "21 10946 4181 6765 True\n",
      "22 17711 6765 10946 True\n",
      "23 28657 10946 17711 True\n",
      "24 46368 17711 28657 True\n",
      "25 75025 28657 46368 True\n",
      "26 121393 46368 75025 True\n",
      "27 196418 75025 121393 True\n",
      "28 317811 121393 196418 True\n",
      "29 514229 196418 317811 True\n",
      "30 832040 317811 514229 True\n",
      "31 1346269 514229 832040 True\n",
      "32 2178309 832040 1346269 True\n",
      "33 3524578 1346269 2178309 True\n",
      "34 5702887 2178309 3524578 True\n",
      "35 9227465 3524578 5702887 True\n",
      "36 14930352 5702887 9227465 True\n",
      "37 24157817 9227465 14930352 True\n",
      "38 39088169 14930352 24157817 True\n",
      "39 63245986 24157817 39088169 True\n",
      "40 102334155 39088169 63245986 True\n",
      "41 165580141 63245986 102334155 True\n",
      "42 267914296 102334155 165580141 True\n",
      "43 433494437 165580141 267914296 True\n",
      "44 701408733 267914296 433494437 True\n",
      "45 1134903170 433494437 701408733 True\n",
      "46 1836311903 701408733 1134903170 True\n"
     ]
    }
   ],
   "source": [
    "for a, b, c in zip(range(45), range(1, 46), range(2, 47)):\n",
    "    print(c, solution.fib(c), solution.fib(a), solution.fib(b), solution.fib(c) == solution.fib(a) + solution.fib(b))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
